#pragma once

namespace violet
{
	template <class K>
	struct binary_search_tree_node
	{
		binary_search_tree_node* _left;
		binary_search_tree_node* _right;
		K _key;

		binary_search_tree_node(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}
	};

	template <class K>
	class binary_search_tree
	{
		typedef binary_search_tree_node<K> node;

	private:
		node* _root = nullptr;

	public:
		//强制生成默认构造
		binary_search_tree() = default;

		//拷贝构造
		binary_search_tree(const binary_search_tree<K>& bst)
		{
			_root = copy(bst._root);
		}

		//赋值运算符重载
		binary_search_tree<K>& operator=(binary_search_tree<K> bst)
		{
			swap(bst._root, _root);
			return *this;
		}

		//析构函数
		~binary_search_tree()
		{
			destroy(_root);
			//destroy参数用引用，_root在destroy里置空
			//_root = nullptr;
		}

		//插入
		bool insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new node(key);
				return true;
			}

			node* parent = nullptr;
			node* cur = _root;
			while (cur != nullptr)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			if (key > parent->_key)
			{
				parent->_right = new node(key);
			}
			else if(key < parent->_key)
			{
				parent->_left = new node(key);
			}

			return true;
		}

		//删除
		bool erase(const K& key)
		{
			node* parent = nullptr;
			node* cur = _root;

			while (cur != nullptr)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						//注意判断cur是否为_root
						if (cur == _root)
						{
							_root = _root->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						
						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = _root->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						
						delete cur;
					}
					else
					{
						//找右树最小节点
						node* parent1 = cur;
						node* cur1 = cur->_right;

						while (cur1->_left != nullptr)
						{
							parent1 = cur1;
							cur1 = cur1->_left;
						}

						cur->_key = cur1->_key;

						//parent1移动了
						if (parent1->_right != cur1)
						{
							parent1->_left = cur1->_right;
						}
						//没移动
						else
						{
							parent1->_right = cur1->_right;
						}

						delete cur1;
					}

					return true;
				}
			}

			return false;
		}

		//查找
		bool find(const K& key)
		{
			node* cur = _root;
			while (cur != nullptr)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

		//递归插入
		bool insert_recursion(const K& key)
		{
			return _insert_recursion(_root, key);
		}

		//递归删除
		bool erase_recursion(const K& key)
		{
			return _erase_recursion(_root, key);
		}

	protected:
		//递归插入
		//注意root引用
		bool _insert_recursion(node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new node(key);
				return true;
			}

			if (root->_key < key)
			{
				return _insert_recursion(root->_right, key);
			}
			else if(root->_key > key)
			{
				return _insert_recursion(root->_left, key);
			}
			else
			{
				return false;
			}
		}

		//递归删除
		bool _erase_recursion(node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}

			if (root->_key < key)
			{
				return _erase_recursion(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _erase_recursion(root->_left, key);
			}
			else
			{
				if (root->_left == nullptr)
				{
					node* temp = root;
					root = root->_right;
					delete temp;
					return true;
				}
				else if (root->_right == nullptr)
				{
					node* temp = root;
					root = root->_left;
					delete temp;
					return true;
				}
				else
				{
					//找左树最大节点
					node* max_left = root->_left;
					while (max_left->_right != nullptr)
					{
						max_left = max_left->_right;
					}

					root->_key = max_left->_key;
					
					//删除max_left
					return _erase_recursion(root->_left, max_left->_key);
				}
			}
		}

		node* copy(node* root)
		{
			if (root == nullptr)
				return nullptr;

			node* new_root = new node(root->_key);
			new_root->_left = copy(root->_left);
			new_root->_right = copy(root->_right);
			return new_root;
		}

		void destroy(node*& root)
		{
			if (root == nullptr)
				return;

			destroy(root->_left);
			destroy(root->_right);
			delete root;
			root = nullptr;
		}
	};
}